package com.liuzhilong.infrastructure.framework.algorithms.algorithms;

import java.util.*;

/**
 * <h2>简单的计算器</h2>
 *<pre>
 *     给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
 *
 * 整数除法仅保留整数部分。
 *
 * 示例 1：
 *
 * 输入：s = "3+2*2"
 * 输出：7
 *
 * 示例 2：
 *
 * 输入：s = " 3/2 "
 * 输出：1
 *
 * 示例 3：
 *
 * 输入：s = " 3+5 / 2 "
 * 输出：5
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/basic-calculator-ii
 *</pre>
 * <p>
 *     计算思想：使用栈进行操作。分为操作符栈和数值栈。
 * </p>
 * <p>
 *     题型特点: 1 运算符都是二元运算符 2 参与计算的都是整数.<br>
 *     <ul>
 *         算法的要点
            <li>1 识别运算符和参与运算的值</li>
            <li>2 运算符的优先级顺序以及有()的参与情况下，优先级要如何处理</li>
            <li>3 当下一个运算符与前一个运算符相比，前一个运算符优先级比较大的时候，触发计算。计算完毕之后再接着进行判断</li>
            <li>4 已经到序列结尾的时候，触发计算</li>
            <li>5 优先计算括号</li>
            <li>6 计算的思想来自Dijkstra的双栈算法</li>
 *      <ul/>
 * </p>
 */
public class SimpleCalculator {
    public static final Map<String, Integer> PRIORITY = new HashMap<>(4);
    static {
        PRIORITY.put("+", 0);
        PRIORITY.put("-", 0);
        PRIORITY.put("*", 1);
        PRIORITY.put("/", 1);
    }
    //操作符栈
    private Deque<String> opt = new LinkedList<>();
    //操作数栈
    private Deque<Integer> value = new LinkedList<>();
    //索引
    private int index = 0;
    private int preOptPriority = -1;
    //限定整数
    public int  calculate(String s) {
        reset();
        boolean needValue = true;
        while (!isEnd(s)){
            if(needValue){
                String nextValue = this.nextToken(s, needValue);
                //直接放入数值栈
                this.value.push(Integer.valueOf(nextValue));
                needValue = false;
                continue;
            }


        }

        return value.pop();
    }

    /**
     * 下一个token 如果已经没有token了 返回null
     * @param s
     * @param value
     * @return
     */
    public String nextToken(String s,boolean value){
        if(!(index<s.length())){
            return null;
        }
        if(value){
            StringBuffer valueBuffer = new StringBuffer();
            char first = s.charAt(index++);
            valueBuffer.append(first);
            while(!isEnd(s)){
                char next = s.charAt(index);
                if(!PRIORITY.containsKey(String.valueOf(next))){
                    valueBuffer.append(next);
                    index++;
                }else {
                    break;
                }
            }
            return valueBuffer.toString();
        }else {
            //符号
            return isEnd(s) ? null : String.valueOf(s.charAt(index++));

        }
    }

    public boolean isEnd(String s){
        return !(index < s.length());
    }
    private void reset(){
        opt.clear();
        value.clear();
        index = 0;
        preOptPriority = -1;
    }

    public static void main(String[] args) {
        String test1 = "1+1";
//        System.out.println(calculate(test1));
        String test2 = "1+1";
        String test3 = "1+1";
        String test4 = "1+1";
        String test5 = "1+1";
    }
}

